# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName  :practice1.py
# @Time      :2025/6/24 22:46
# @Author    :aiyimu
from typing import List


class Solution:
    # 基本二分查找
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

    # 34. 在排序数组中查找元素的第一个和最后一个位置[https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/]
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        """
            - 找左端点，数组被分成两部分：① 小于t ② 大于等于t
            - 找右端点，数组分为两部分：① 小于等于t ② 大于t
        """
        n = len(nums)

        # 找左端点
        left, right = 0, n - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        # 左端点检查
        if left < n and nums[left] == target:
            begin = left
        else:
            return [-1, -1]

        # 找右端点
        left, right = 0, n - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1

        # 右端点检查
        end = right

        return [begin, end]

    # [69.x的平方根](https: // leetcode.cn / problems / sqrtx / description /)
    def mySqrt(self, x: int) -> int:
        # 边界情况
        if x < 1:
            return 0

        left, right = 0, x
        while left < right:
            # 两指针相遇时跳出循环
            mid = int(left + (right - left + 1) / 2)
            if mid * mid <= x:
                left = mid
            else:
                right = mid - 1

        return int(left)  # 只保留整数部分

    # [35.搜索插入位置](https://leetcode.cn/problems/search-insert-position/description/)
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = int(left + (right - left + 1) / 2)
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid

        # 两指针相遇
        if nums[left] < target:  # 目标值不存在时：
            return left + 1
        else:
            return left

    # [852.山脉数组的峰顶索引](https: // leetcode.cn / problems / peak - index - in -a - mountain - array / description /)
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        # 峰值元素的规律：
        # {a[i]<a[i+1]} p {a[i]>a[i+1]}
        if len(arr) < 3:
            return -1

        # 将peak作为左区间的右侧端点
        left, right = 0, len(arr) - 1
        while left < right:
            mid = int(left + (right - left) / 2)
            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            elif arr[mid] >= arr[mid + 1]:
                right = mid

        return right

        # [162.寻找峰值](https://leetcode.cn/problems/find-peak-element/description/)
        def findPeakElement(self, nums):
            n = len(nums)
            left, right = 0, n - 1
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] <= nums[mid + 1]:  # 峰值在右侧
                    left = mid + 1
                else:
                    right = mid
            return right

        # [153.寻找旋转排序数组中的最小值](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/)
        def findMin(self, nums):
            n = len(nums)
            left, right = 0, n - 1
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] > nums[n - 1]:  # 左侧区间
                    left = mid + 1
                else:
                    right = mid
            return nums[right]